#include <stdio.h>
#include <stdlib.h>
#include "string.h"

//定义最大顶点数，本常量在定义MGraph结构体的顶点和边时，都必须被用到
#define MVNum 100
typedef enum{FALSE,TRUE} Boolean;

typedef char VerTexType;      //假设顶点的数据类型为字符型
typedef int ArcType;          //假设边的权值类型为整型

typedef struct{
    VerTexType vexs[MVNum];     //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum, arcnum;         //图的当前点数和边数
} MGraph;

// ====查找图G的顶点的编号====
// 编号为构建图G时每个顶点的读入顺序，从0开始。
// 查找到指定顶点名字时，返回对应编号；找不到时，返回-1 。
int locate_vertex(MGraph * G, char vertex_name) {
    for (int i = 0; i < G->vexnum;++i) {
        if( vertex_name == G->vexs[i] ){
            return i;
        }
    }
    return -1;
}

//=========建立邻接矩阵=======
// 参数 G_pp 是尚未被初始化的 (指向 (指向 MGraph 的指针) 的指针)
// 参数 graph_data_filename 是存储如下格式的图数据的文件名（字符串）：
/*
 * 顶点数 边数
 * 顶点名字序列（用a b c d e 等字符命名）
 * a b // 边1
 * a c // 边2
 * d e // 边3
 */
void create_graph(MGraph ** G_pp, char * graph_data_filename)
{
    FILE * fp;
    size_t len = 0;
    ssize_t read;

    int num_nodes, num_edges;
    *G_pp = (MGraph *) malloc(sizeof (MGraph));
    if(*G_pp==NULL){
        printf("初始化失败");
    }
    // 打开由 graph_data_filename变量 指定的文件名
    fp = fopen(graph_data_filename, "r");
    if (fp == NULL)
    {
        printf("失败");
        exit(EXIT_FAILURE);
    }

    // 从文件名由 graph_data_filename 变量所指定的文件里读取顶点数和边数
    // fscanf函数 的用法类似scanf
    fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
    // 后续的内容读取参考上一句 fscanf 函数
    for (int i = 0; i < num_nodes; ++i) {
        fscanf(fp,"%c\n",&((*G_pp)->vexs[i]));
    }
    (*G_pp)->vexnum = num_nodes;
    (*G_pp)->arcnum  = num_edges;
    for (int i = 0; i < num_edges; ++i) {
        char j,k;
        fscanf(fp,"%c %c\n",&j,&k);
        int a = locate_vertex(*G_pp,j),b= locate_vertex(*G_pp,k);
        (*G_pp)->arcs[a][b]=1;
        (*G_pp)->arcs[b][a]=1;
    }
    // 实现开始：可以自行定义变量，但是不要删掉或者更改对fopen和fclose的调用

    // 如上，用fscanf从fp里读取字符

    // 实现结束


    // 关闭打开的文件
    fclose(fp);
}

//========dfs：深度优先遍历的递归算法======
// 参数 G：指向MGraph类型的变量的指针。
// 参数 i: 当前被访问的顶点 i。i是顶点在给出的 顶点名字序列 里从0开始的位置编号：比如顶点 b 在 顶点序列 a b c d e f中的位置编号是 1。
// 参数 result_sequence: 用于记录在 当全局访问顺序为 visited_order 时，被访问的结点名字（字符）。
// 参数 visited_order: 当前顶点被访问的全局顺序
void dfs(MGraph *G, int i, Boolean visited[], char * result_sequence, int * visited_order)
{
    visited[i]=TRUE;
    char *s;
    s=(char *) malloc(2);
    s[0]=G->vexs[i];
    s[1]='\0';
    *visited_order=G->vexs[i];
    strcat(result_sequence,s);
    for (int j=0 ;j<G->vexnum;j++) {
        if(G->arcs[i][j]==1 && visited[j]==FALSE){
            dfs(G,j,visited,result_sequence,visited_order);
        }
    }
}

//===========bfs：广度优先遍历=======
// 参数 G：指向MGraph的指针
// 参数 k: 当前被访问的顶点 k。k是顶点在给出的 顶点名字序列 里从0开始的位置编号；比如顶点 b 在 顶点序列 a b c d e f中的位置编号是 1。
// 参数 visited_sequence: 用于记录在广度优先遍历时，依次被访问的顶点的名字（字符）
void bfs(MGraph *G, int k, Boolean visited[], char * visited_sequence)
{        char *s;
    s=(char *) malloc(2 );
    s[0]=G->vexs[k];
    s[1]='\0';
    visited[k] = TRUE;
    strcat(visited_sequence,s);
    char str=*visited_sequence;
    int i =0;
    while (str!='\0'){
        for(int j = 0;j<G->vexnum;j++) {
            if (G->arcs[k][j] == 1 && visited[j] == FALSE) {
                visited[j] = TRUE;
                char *s;
                s = (char *) malloc(2);
                s[0] = G->vexs[j];
                s[1] = '\0';
                strcat(visited_sequence, s);
            }
        }
        i++;
        str = *(visited_sequence+i);
        if(str!='\0')
            k = locate_vertex(G,str);

    }

}

// 以下 main 函数的实现，供参考。

int main () {
    int i;
    MGraph *G;
    Boolean visited[MVNum];

    create_graph(&G, "D:/zhaoyu/lab6/graph_data.txt"); //建立邻接矩阵
//    for(int i = 0;i<G->vexnum;i++){
//        for(int j = 0;j<G->vexnum;j++){
//            if(G->arcs[i][j]==1){
//                printf("1\t");
//            } else{
//                printf("0\t");
//            }
//            if(j==G->vexnum-1){
//                printf("\n");
//            }
//        }
//    }
    for(i=0; i<MVNum; i++) {
        visited[i] = FALSE;
    }
    char dfs_sequence[MVNum] = {'\0'};
    int visited_order = 0;
    dfs(G, 0, visited, dfs_sequence, &visited_order); //深度优先遍历。 应该输出：abdhecfg
    printf("Print Graph DFS: ");
    printf("%s\n", dfs_sequence);
    printf("\n");


    for(i=0; i<MVNum; i++) {
        visited[i] = FALSE;
    }
    char bfs_sequence[MVNum] = {'\0'};
    bfs(G, 0, visited, bfs_sequence); //以序号为0的顶点开始广度优先遍历。应该输出：abcdefgh
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence);
    printf("\n");
    for(i=0; i<MVNum; i++) {
        visited[i] = FALSE;
    }
    char bfs_sequence2[MVNum] = {'\0'};
    bfs(G, 3, visited, bfs_sequence2); //以序号为3的顶点开始广度优先遍历。应该输出：dbhaecfg
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence2);
    printf("\n");
    return 0;
}
